/*
 * Starting in the top left corner of a 2x2 grid,
 * there are 6 routes (without backtracking)
 * to the bottom right corner.
 * 
 * Start _____
 *       | | |
 *       -----
 *       | | |
 *       ----- End
 * 
 * right, right, down, down
 * right, down, right, down
 * right, down, down, right
 * down, right, right, down
 * down, right, down, right
 * down, down, right, right
 * 
 * How many routes are there through a 20x20 grid?
 */

package pj1;

import java.math.BigInteger;

class Problem15 {

	static final int problem = 20;
	
	public static void main(String[] args) {
		BigInteger result = BigInteger.ONE;
		
		// all the possible ways from top left corner to bottom right corner
		for (Integer i = 1; i <= problem*2; i++) {
			result = result.multiply(new BigInteger(i.toString()));
		}
		
		// going right then down and down then right removing possibilities
		for (Integer i =1; i <= problem; i++) {
			result = result.divide(new BigInteger(i.toString()));
			result = result.divide(new BigInteger(i.toString()));
		}
		System.out.println(result);		
	}
}
